package W328;

/**
 * @author zxc
 * @date 2023/01/15 10:52
 **/

import java.util.Arrays;

/**
 * 题目 ：统计好子数组的数目
 * 题目详述 ：
 * 给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中 好 子数组的数目。
 * 一个子数组 arr 如果有 至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个 好 子数组。
 * 注意 ：子数组 是原数组中一段连续 非空 的元素序列。
 *
 * 提示：
 * 1 <= nums.length <= 10的5次方
 * 1 <= nums[i], k <= 10的9次方
 */
public class CountGood {
    /**
     * 思路 ：
     * 即，双指针思想，指针p1和p2分别指向子数组的初始元素位置和尾元素位置；
     */
    // 暴力法 ：即，获取当前nums数组的所有可能子数组，然后再次对于每个子数组去判断是否 至少有k对下标满足 i < j 且 arr[i] == arr[j] 条件；
    public long countGood(int[] nums, int k) {
        // 使用long类型来存储，防止使用int类型来统计好子数组的数目，可能会出现溢出的情况；
        long goodCount = 0L;
        // 由于nums数组的长度length为[0 , 10的5次方]，即若是仅仅使用int类型的指针便能够遍历nums数组中的所有元素；
        int length = nums.length;
        // 对于数组中的所有元素进行排序；（从小到大进行排序）
        Arrays.sort(nums);
        for(int p1 = 0 ; p1 < length ; p1++){
            long count = 0L;
            // 即，首先定住子数组的初始元素位置，将指向子数组尾部元素的指针逐步后移；
            for(int p2 = p1 + 1; p2 < length ; p2++){
                // 两层for循环，实现获取当前遍历数组的所有子数组；
//                if(count >= k){
//                    // 在子数组的初始元素已经固定，子数组的尾部元素不断地向后进行遍历的情况下 ：
//                    // 若是在某一时刻，数组元素中满足 i < j 且 arr[i] == arr[j]条件的数目 >= k时，那么后续子数组必然也是好子数组；
////                    System.out.println("p1 = " + p1 + "p2 = " + p2);
//                    goodCount += length - p2;
//                    break;
//                }
                // count函数作用 ：用来统计当前子数组中满足 i < j 且 arr[i] == arr[j]条件的数目；
                count = a(nums , p1 , p2);
                if(count >= k){
                    System.out.println("p1 = " + p1 + "p2 = " + p2);
                    goodCount += length - p2 + 1;
                }
            }
        }
        // 遍历完所有的子数组后，直接返回goodCount（用来统计好子数组的数目）即可；
        return goodCount;
    }
    // 返回当前子数组中，满足 i < j 且 arr[i] == arr[j]条件的数目;
    private long a(int[] arr, int p1, int p2) {
        // 用于统计当前子数组arr中，满足 i < j 且 arr[i] == arr[j]条件的数目
        long count = 0L;
        for(int i = p1 ; i <= p2 ; i++){
            for(int j = i + 1 ; j <= p2 ; j++){
                if(arr[i] == arr[j]){
                    count++;
                }
            }
        }
        // 返回当前子数组中所统计到的满足 i < j 且 arr[i] == arr[j]条件的数目
        return count;
    }
}
